import java.util.ArrayList;
import java.util.List;

public class Solution120 {
    /**
     * 给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
     * 例如，给定三角形：
     * [
     * [2],
     * [3,4],
     * [6,5,7],
     * [4,1,8,3]
     * ]
     * 自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
     */
    public int minimumTotal(List<List<Integer>> triangle) {
        int deep = triangle.size();
        if (deep == 0) return 0;
        minimumTotalCore(triangle, deep);
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < deep; i++) {
            min = Math.min(min, triangle.get(deep - 1).get(i));
        }
        return min;
    }

    public void minimumTotalCore(List<List<Integer>> triangle, int deep) {
        deep--;
        if (deep == 0) return;
        minimumTotalCore(triangle, deep);
        int len = triangle.get(deep).size();
        triangle.get(deep).set(0, triangle.get(deep - 1).get(0) + triangle.get(deep).get(0));
        triangle.get(deep).set(len - 1, triangle.get(deep - 1).get(len - 2) + triangle.get(deep).get(len - 1));
        for (int i = 1; i < len - 1; i++) {
            triangle.get(deep).set(i, triangle.get(deep).get(i) + Math.min(triangle.get(deep - 1).get(i - 1), triangle.get(deep - 1).get(i)));
        }
    }

    public static void main(String[] args) {
        Solution120 test = new Solution120();
        List<List<Integer>> triangle = new ArrayList<>();
        List<Integer> list1 = new ArrayList<>();
        list1.add(2);
        List<Integer> list2 = new ArrayList<>();
        list2.add(3);
        list2.add(4);
        List<Integer> list3 = new ArrayList<>();
        list3.add(6);
        list3.add(5);
        list3.add(7);
        triangle.add(list1);
        triangle.add(list2);
        triangle.add(list3);
        System.out.println(test.minimumTotal(triangle));
    }
}
